// quick_sort_industrial.c
#include <stdio.h>
#include <stdlib.h>
#include "test.h"

#define INSERTION_SORT_THRESHOLD 10

// 交换两个元素的值
void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

// 插入排序
void insertionSort(int arr[], int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// 三数取中选择基准元素
int medianOfThree(int arr[], int left, int right) {
    int mid = left + (right - left) / 2;
    if ((arr[left] <= arr[mid] && arr[mid] <= arr[right]) || (arr[right] <= arr[mid] && arr[mid] <= arr[left]))
        return mid;
    else if ((arr[mid] <= arr[left] && arr[left] <= arr[right]) || (arr[right] <= arr[left] && arr[left] <= arr[mid]))
        return left;
    else
        return right;
}

// 分区函数
int partition(int arr[], int left, int right) {
    int pivotIndex = medianOfThree(arr, left, right);
    swap(&arr[pivotIndex], &arr[right]);  // 将基准元素放到最后
    int pivot = arr[right];
    int i = left - 1;

    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[right]);      // 将基准元素放到正确的位置
    return i + 1;
}

// 快速排序函数
void quickSort(int arr[], int left, int right) {
    while (left < right) {
        if (right - left + 1 <= INSERTION_SORT_THRESHOLD) {
            insertionSort(arr, left, right);
            break;
        } else {
            int pivotIndex = partition(arr, left, right);
            if (pivotIndex - left < right - pivotIndex) {
                quickSort(arr, left, pivotIndex - 1);
                left = pivotIndex + 1;
            } else {
                quickSort(arr, pivotIndex + 1, right);
                right = pivotIndex - 1;
            }
        }
    }
}

// 打印数组函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
void for_test(int arr[], int n) {
    quickSort(arr, 0, n - 1);
}
   

// 主函数
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: \n");
    printArray(arr, n);
    
    printf("\n");

    benchmark(for_test);


    return 0;
}